#include <stdio.h>
#include <_array.h>

int find_dup(int * a, int size)
{
    int i;
    int temp;

    for (i = 0; i < size;) {
	// for debugging and understanding
	printf("i: %d, ", i); print_array(a, size);
	if (a[i] == i+1) {
	    i++;
	    if (a[i] == a[i-1]) // elements before a[i] are already sorted
	    {
	        printf("return from 1\n");
	        return a[i];
	    }
	}
	else {
	    temp = a[i];
	    if (temp == a[temp-1]) // avoid infinite loop: i=1, array=1,3,3
	    {
		printf("return from 2\n");
		return temp;
	    }
	    a[i] = a[temp-1];
	    a[temp-1] = temp;
	}
    }

    return -1;
}

void print_array(int * a, int size)
{
    int i;

    if (!a || size <= 0)
	return;

    printf("array: ");
    for (i = 0; i < size; i++) {
       printf("%d\t", a[i]);	
       if (i && !(i % 8))
	   printf("\n");
    }
    printf("\n");
}

/*
 * compact a sorted array, return the length of the new array.
 * e.g.: from {1,3,3,7,8,8,8} to {1,3,7,8}, with a length of 4 returned
 *
 */
int compact(int * a, int n)
{
#if 0
    int i, j;

    if (!a || n <= 0)
	return -1;

    i = 0; j = 0;
    while (j < n) {
	while (j+1 < n && a[j] == a[j+1])
	    j++;
	a[i++] = a[j++];
    }

    return i;
#else
    int insert = 1;
    int current;

    // since must remain a[0] in place
    for (current = 1; current < n; current++) {
	if ( a[current] != a[insert - 1]) {
	    a[insert++] = a[current++];
	}
	else
	    current++;
    }

    return insert;
#endif
}
